Algorithmes génétiques (AG) sont des heuristiques stochastiques de recherche globale inspirées des principes de l'évolution naturelle, notamment la « survie du plus apte » darwinienne et la recombinaison génétique.
1. Cadres de représentation
- Algorithmes génétiques canoniques : Utilisent des chaînes binaires ou en code Gray pour encoder les variables de décision.
- Algorithmes génétiques à codage réel (AGCR) : Manipulent directement des vecteurs à virgule flottante, souvent plus efficaces pour l'optimisation continue.
2. La boucle évolutionnaire
Processus itératif d'évaluation, de sélection et de reproduction. Un concept crucial est la distinction entre le génotype (la chaîne binaire encodée/chromosomique) et le phénotype (la valeur décodée de la variable de décision dans l'espace du problème réel).
La correspondance entre une chaîne binaire et une valeur réelle $x \in [a, b]$ est donnée par :
$$x = a + \frac{valeur\_décimale \times (b - a)}{2^L - 1}$$
Où $L$ est la longueur en bits du chromosome.
Cliffords de Hamming
Faites attention aux cliffords de Hamming dans le codage binaire standard — situations où des nombres décimaux adjacents (comme 7 et 8) ont des motifs binaires radicalement différents (
0111 contre 1000), ce qui rend difficile pour l'AG effectuer des recherches localisées.
Implémentation Python : Décodage binaire vers réel
Question 1
Pourquoi le codage de Gray est-il souvent préféré au codage binaire standard dans les AG ?
Question 2
Si la probabilité de mutation (p) est trop élevée (par exemple, p = 0,5), quel est le résultat probable ?
Étude de cas : Optimisation d'un composant de pont
Lisez le scénario ci-dessous et répondez aux questions.
Vous optimisez la conception d'un composant de pont dont la variable décisionnelle est l'"épaisseur du matériau".
- L'épaisseur doit être comprise entre 0,0 mm et 10,23 mm.
- Vous utilisez un AG canonique avec une représentation en chaîne binaire de 10 bits bits.
Q
1. Si un individu possède le chromosome
0000000000, quelle est l'épaisseur décodée ?Réponse : 0,0 mm
La chaîne binaire
La chaîne binaire
0000000000 vaut 0 en décimal. En utilisant la formule $x = a + \frac{décimal \times (b-a)}{2^L - 1}$, nous obtenons $0,0 + \frac{0 \times (10,23 - 0,0)}{1023} = 0,0$.
Q
2. Calculez la précision de recherche (le changement minimal possible de l'épaisseur) pour cette configuration de 10 bits.
Réponse : 0,01 mm
La précision est définie par la plage divisée par la valeur décimale maximale possible. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01\,\text{mm}$.
La précision est définie par la plage divisée par la valeur décimale maximale possible. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01\,\text{mm}$.
Q
3. Lors de la sélection, l'individu A a une adaptation de 10 et l'individu B une adaptation de 30. Avec la sélection par roue de roulette, quelle est la probabilité que B soit choisi plutôt que A ?
Réponse : 75 %
Adaptation totale = $10 + 30 = 40$. Probabilité de choisir B = $\frac{30}{40} = 0,75$ ou 75 %. (Ratio 3:1).
Adaptation totale = $10 + 30 = 40$. Probabilité de choisir B = $\frac{30}{40} = 0,75$ ou 75 %. (Ratio 3:1).